package solved.recfun
import common._

object Main {
  def main(args: Array[String]) {
    println("Pascal's Triangle")
    for (row <- 0 to 10) {
      for (col <- 0 to row)
        print(pascal(col, row) + " ")
      println()
    }
  }

  /**
   * Exercise 1
   */
  def pascal(c: Int, r: Int): Int = {
    def isExtreme : Boolean = c == r || c == 0
    
    if (isExtreme) 1
    else pascal(c, r-1) + pascal(c-1, r-1)
  }

  /**
   * Exercise 2
   */
  def balance(chars: List[Char]): Boolean = {
    def innerBalanced (openParenthesis : Int, closeParenthesis : Int, chars : List[Char]) : Boolean= {
      if (chars.isEmpty) openParenthesis == closeParenthesis
      else chars.head match {
        case '(' => innerBalanced(openParenthesis+1, closeParenthesis, chars.tail)
        case ')' => if (openParenthesis > closeParenthesis) innerBalanced(openParenthesis, closeParenthesis+1, chars.tail)
    	  			else false
        case _ => innerBalanced (openParenthesis, closeParenthesis, chars.tail)
      }
    }
    
    innerBalanced (0, 0, chars);
  }

  /**
   * Exercise 3
   */
  def countChange(money: Int, coins: List[Int]): Int = {
    def innerCountChange(money : Int, coins : List[Int], currentMoney : Int) : Int = {
      if (coins.isEmpty) 0
      else{
    	  val nextAmmount = currentMoney + coins.head
		  if (nextAmmount == money) 1
		  else if (nextAmmount > money) 0
		  else innerCountChange(money, coins, nextAmmount) + innerCountChange(money, coins.tail, currentMoney)
      }
    }
    
    if (coins.isEmpty) 0
    else innerCountChange(money, coins.sorted, 0)
  }
}
